package me.project.offer;

/**
 * 求菲波那契数列的第 n 项，n <= 39。
 * f(0) = 0
 * f(1) = 1
 * f(n) = f(n-2) + f(n-1)
 *
 * @author mbryce
 * @date 2018/7/1
 */
public class Solution10_1th {
    /**
     * AC
     * 运行时间：16 ms
     * 占用内存：9256K
     * 空间+ 时间：O(N) + O(N)
     *
     *
     * 缓存计算到的 f(n)
     *
     * @param n
     * @return
     */
    public int Fibonacci(int n) {
        if (n <= 1)
            return n;
        int[] fib = new int[n + 1];
        fib[0] = 0;
        fib[1] = 1;
        for (int i = 2; i <= n; i++) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }
        return fib[n];
    }

    /**
     * AC
     * 运行时间：18ms
     * 占用内存：9384k
     * 空间+ 时间： O(1) + O(N)
     *
     * 重复利用前两个已经算计的值
     *
     * @param n
     * @return
     */
    public int Fibonacci2(int n) {
        if (n <= 1)
            return n;
        int fib = 0;
        int pre1 = 0;
        int pre2 = 1;
        for (int i = 2; i <= n; i++) {
            fib = pre2 + pre1;
            pre1 = pre2;
            pre2 = fib;
        }
        return fib;
    }


}
